package com.bolins.math.insertion;

import com.bolins.math.Sortor;

/**
 * 插入排序，实现排序接口
 * 
 * 增量方法
 * 
 * @author liuys
 * 
 * 伪代码：
 * 
 * for i <-- 1 to length(input)
 *  	do key <-- input[i]
 *  		####将input[i]插入到排好序的序列input[0...i-1]中
 *  	   j <-- i-1
 *  	   while(j>=0 and input[j]>key)
 * 				do input[j+1] <-- input[j]
 * 				   j <-- j-1;
 * 		   input[j+1] <-- key
 */
public class InsertionSortor implements Sortor {

	/**
	 * 插入排序算法实现（升序）
	 */
	@Override
	public int[] exeSort(int[] input) {
		for (int i = 1; i < input.length; i++) {// 遍历输入实例1...length-1,
			int key = input[i];				// 将当前要排序的数放到中间变量中去
			int j = i - 1;						// 取得将要与key比较的数的下标
			
			while (j >= 0 && input[j] > key) {	// 判断下标是否越界及下标指向的数是否大于要排序的数，如果大于
				input[j + 1] = input[j];		// 则被比较的数在数组中右移一位，并继续让Key与之前面一个数比较，否则停止比较。
				j = j - 1;
			}
			input[j + 1] = key;					//将Key插入到最后一次移动的数的原始位置上
		}
		return input;
	}
}
